﻿Основные понятия
admin|2009/01/18 19:18:49
##PAGE##
{TOC}

Система FP включает в себя следующее: 

#множество O объектов; 
#множество F функций f, которые отображают объекты на объекты; 
#операцию, применение; 
#множество Γ комбинирующих форм; они служат для комбинирования существующих функций или объектов для формирования новых функций из F; Т.е комбинируюшая форма - это функционал, отображающий функции и объекты на функции. 
#множество D описаний, определяющих некоторое функции в F и присваивающих каждой из них имя.

===Объекты===

Объект x является либо: 

# неопределенностью или основой ⊥; 
# атомом; Мы будем считать, что множество A атомов состоит из непустых конечных строк из прописных букв, целых чисел и специальных атомов T и F, обозначающих истину и ложь. 
# последовательностью(кортежем) <esc><</esc>x<sub>1</sub>,…,x<sub>n</sub>>, элементы которой представляют собой атомы или другие кортежи, но не ⊥; ∅ обозначает пустой кортеж.

Примеры объектов.

⊥; 1.5; ∅; <esc><AB,1,2,3></esc>; <esc><A,⊥></esc> = ⊥ 


===Применение===

Система FP включает единственную операцию, применение или апплицирование. Если f -функция из F, x - объект, то f:x - объект, результат применения f к x. 

Примеры 

+:<1, 2> = 3; <esc>tl:<A,B,GH> = <B,GH> </esc>


===Функции===

Любая функция из F будет либо: 

#Примитивной функцией, поставляемой вместе с системой; Обозначим множество таких функций через P. В таблице 2.3 приведено несколько примеров. Существенным, является то, что ”хорошими” считаются мощные широкоприменимые примитивные функции. 
#Описываемой(смотри ниже); 
#Функциональной формой, т.е. функцией полученной путем применения одной или нескольких комбинирующих форм из Γ к уже определенным функциям и объектам. 

На все функции наложено важное ограничение: все функции являются строгими, то есть ∀ f, f : ⊥ = ⊥. 


{| border="1"
! Функция !! Описание и примеры 
|-
| 1s, 2s , … 
| Функции выбора: селектор i примененный к объекту x вернет i-ый элемент x, если x это последовательность длинны не меньше i, или ⊥ в противном случае. (Мы используем одно и то же обозначение для объекта 1 функции-селектора 1. Из контекста всегда понятно что имеется ввиду.) 
|- 
| tl 
| Функция ”хвост”. Если ее аргументом является непустой список, то возвращает его целиком, но без первого элемента. В противном случае ⊥. Пример: tl : <3,4> = <4>. 
|- 
| id 
| Тождественная функция : id : x = x для всех x из O. 
|- 
| eq 
| Тест на равенство: eq : x возвращает Т, если x - пара тождественных объектов, F - если пара разных объектов, ⊥ в противном случае. Примеры: eq : <<A,3>,<A,3>> = T; eq : <A,3> = F; eq : <3,3,3> = ⊥. 
|- 
| gt, ge, lt, le 
| Отношения порядка на целых числах. Например: gt : <3,2> = T; gt :  <3,A> = ⊥; gt : <3,2,1> = ⊥.
|- 
| +, - , ×, ї 
| Арифметические операции на парах целых чисел. Примеры: + : <3,4> = 7; + : <3> = ⊥; + : <3,A> = ⊥. 
|- 
| addl, subl 
| Добавить и отнять единицу. Определена на целых.
|} 
<sub>Таблица 2.1:  Примеры примитивных функций </sub>
 

На примере нескольких весьма полезных функций, которые обычно относят к примитивным, покажем что такое описываемые функции. Мы употребляем вариант условного выражение Маккарти: 


Важные примеры: 

{|
! Распределение слева, distl 
| distl : x ≡ x=<y,∅>  →  ∅; x=<y, <z1 ,…,zn>> →  <<y,z1>,…,<y,zn>>; ⊥ 
|-
! Распределение справа, distr 
| distr : x ≡ x=<∅,y>  →  ∅; x=<<y1 , …,yn>,z> →  <<y1,z>,…,<yn,z>>; ⊥ 
|-
! Присоединить слева, apndl или ⊂ 
| apndl : x ≡ x=<y,∅>  →  <y>; x=<y,<z1,…,zn>> →  <y,z1…,zn>; ⊥ 
|-
! Присоединить справа, apndr или ⊃ 
| apndr : x ≡ x=<∅,z>  →  <z>; x=<<y1,…,yn>,z> →  <y1…,yn,z>; ⊥ 
|-
! Транспонирование, trans 
| trans : x ≡ x=<∅,…,∅> →  <∅>; x=<x1 , … ,xn> →  <y1,…,yn>; ⊥
где 
xi =<xi1 , …,xim> и yj=<x1j,…,xnj> 
|-
! Тест нуля, null 
| null : x ≡ x=∅ →  T; x≠⊥→  F; ⊥ 
|-
! Обращение, reverse 
| reverse : x ≡ x=∅ →∅; x=<x1,…,xn> → <xn , … , x1 >; ⊥
|}

===Комбинирующие формы===

Определим здесь основные комбинирующие формы, используемые в FP. Для каждой комбинирующей формы покажем, какую функциональную форму она образует после подстановки в нее параметров. Здесь p,f,g с индексами и без них - произвольные функции, x<sub>1</sub> ..x<sub>n</sub>,y — произвольные объекты. 

''Композиция ''

 <math>(f \circ g): x \equiv  f : g : x </math>

Конструкция

 <math>[f_1,\ldots,f_n]~:~x\equiv \langle f_1:x,\ldots,f_n:x\rangle</math>


''Условие ''

 <math>(p\longrightarrow f;g):x\equiv (p:x)=T\rightarrow f:x; (p:x)=F\rightarrow g:x; \bot </math>

''Константа'' 

<math>\bar{x}:y\equiv \bot\rightarrow\bot; x</math>

здесь ''x'' - объектный параметр. 

''Включение, она же правая свертка ''

<math>
/f:x\equiv x=\langle x_1\rangle\rightarrow x_1;
             x=\langle x_1,\ldots, x_n\rangle  \&  n\geq2\rightarrow f:\langle x_1, /f:\langle
             x_2,\ldots,x_n\rangle\rangle;
             \bot
</math>


''Левая свертка ''

<math>
\backslash f:x\equiv x=\langle x_1\rangle\rightarrow x_1;
              x=\langle x_1,\ldots, x_n\rangle \& n\geq2\rightarrow f:\langle\backslash f:\langle
             x_1,\ldots,x_{n-1}\rangle, x_n\rangle;
             \bot
</math>


''Применить ко всем, она же map ''

<math>
\alpha f:x\equiv x=\emptyset\rightarrow\emptyset;
                  x=\langle x_1,\ldots, x_n\rangle\rightarrow\langle f:x_1,\ldots,f:x_n\rangle
</math>


''Двоичное в единичное ''

<math>(bu fx):y =f~:~\langle x,y\rangle</math>
здесь ''x'' - объектный параметр. 

Таким образом 
<math>(bu+1):x=1+x</math>


''Цикл с предусловием, while ''

<math>
(while ~p ~f)~:~x\equiv p~:~x = T\rightarrow(while~p~f):(f~:~x);\ p:x=F\rightarrow x;\bot
</math>



===Определения===

Определением в системе FP является выражение вида 
'''Def l = r'''

где левая часть l представляет собой еще не использованный символ функции, а правая часть является функциональной формой, которая также может зависеть от l. Оно выражает в первую очередь тот факт, что при вычислении аппликации '''l : r''', в первую очередь нужно заменить l на правую часть определения.Множество '''D''' определений корректно, если никакие две левые части не совпадают. 

''Примеры. ''
#Функция lastl порождает последний элемент последовательности. 
<math>\text{Def}\ lastl = 1\circ reverse</math>
#Функция last делает тоже самое, но определена по-другому. 
<math>\text{Def}\ last = null\circ tl\rightarrow1;\ last\circ tl</math>

В заключение этого раздела, заметим, что определения - не единственный способ описать функцию. В статье [/ScrewTurnWiki/Refrences.ashx|2] Джон Бэкус предложил иной, более ясный способ определения функций, названный им обобщенными определениями. Нотация близка к нотации λ-выражений, и будет приятнее программистам имеющим опыт функционального программирования на языках типа Лиспа. 

===Семантика FP-программ===

Классический вариант FP, рассматриваемый здесь имеет несложную операционную семантику. Все что нам нужно - это умение вычислять аппликацию f : x для любого объекта x и любой функции f. Для f имеются четыре возможности: 

f является примитивной функцией; 
f является функциональной формой; 
в D имеется одно определение, Def f  = r; 
ни один из предыдущих вариантов не имеет места.

Если f - примитивная функция, то мы располагаем ее определением и знаем, как ее применять. Если f - функциональная форма, то определение формы содержит информацию о том, как вычислять f  : x в терминах параметров формы, что может быть сделано при дальнейшем использовании этих правил. Если функция f определена согласно Def f =r, как в (3), то для отыскания f  : x мы вычисляем r : x, а это можно сделать дальнейшим применением данных правил. Если ни один из рассмотренных вариантов не имеет места, то f  : x=⊥. Разумеется, работа по этим правилам может не завершиться при некоторых f и x; в таком случае мы присваиваем значение f  : x=⊥. 

В работе Вильямса  было показано, что эта операционная семантика соответствует семантики неподвижной точки, то есть, что функция, заданная опеределением Def f = E(f) действительно будет неподвижной точкой функционала E. Отметим также, что для FP несложно задается и денотационная семантика.
 
 
 
 
  
   
